package cn.edu.njust.alg.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode_118_pascalstriangle {

	/*
	 * Given numRows, generate the first numRows of Pascal's triangle.
	 * 
	 * For example, given numRows = 5, Return
	 * 
	 * [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
	 */
	public List<List<Integer>> generate(int numRows) {

		List<List<Integer>> pascals = new ArrayList<List<Integer>>();
		if (numRows <= 0) {
			return pascals;
		}
		List<Integer> list = new ArrayList<Integer>();
		list.add(1);
		pascals.add(list);
		
		for (int i = 1; i <= numRows-1; i++) {
			list = new ArrayList<Integer>();
			List<Integer>prelist=pascals.get(i-1);
			list.add(1);
			for(int j=1;j<prelist.size();j++){
				int s = prelist.get(j-1)+prelist.get(j);
				list.add(s);
			}
			list.add(1);
			pascals.add(list);
		}

		return pascals;
	}

	public static void main(String[] args) {
		List<List<Integer>> pascals = new Leetcode_118_pascalstriangle().generate(4);
		System.out.println("[");
		for(List<Integer> list :pascals ){
			System.out.print("[");
			
			for(int e:list){
				System.out.print(e+" ");
			}
			
			System.out.print("]");
		}
		System.out.println();
		System.out.println("]");

	}

}
